import heapq
from typing import List


class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        queue = [(grid[0][0],(0,0))]
        inf = float('inf')
        Early = [[inf for _ in range(n)] for _ in range(n)]
        Early[0][0] = grid[0][0]
        while queue:
            cost,(x,y) = heapq.heappop(queue)
            if Early[x][y] < cost: continue
            for nx,ny in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
                if nx <0 or nx >= n: continue
                if ny <0 or ny >= n: continue
                nex = max(grid[nx][ny], cost)
                if nex >= Early[nx][ny]: continue
                Early[nx][ny] = nex
                heapq.heappush(queue, (nex, (nx,ny)))
        return Early[n-1][n-1]

if __name__ == '__main__':
    s = Solution()
    r = s.swimInWater([[0,2],[1,3]])
    print(r)